package LinkTest;

import java.util.LinkedList;
import  java.util.Stack;
public class LinkTest {
    static class ListNode {
    int val;
    ListNode next = null;
    public ListNode(int val) {
      this.val = val;
    }
  }
    //链表节点每k个一组翻转
    public static ListNode  reverseKGroup (ListNode head, int k) {
        // write code here
        if(head==null||k==1){
            return head;
        }
        ListNode cur=head;
        ListNode n1=new ListNode(0);
        int l=0;
        while(cur!=null){
            l++;
            cur=cur.next;
        }
        int g=l/k;
        n1.next=head;
        cur=head;
        ListNode o=n1;
        Stack<ListNode> s=new Stack<>();
        while(l>=k){
            for(int i=0;i<k;i++){
                s.push(cur);
                cur=cur.next;
            }
            while(!s.isEmpty()){
                o.next=s.pop();
                o=o.next;
            }
            o.next=cur;
            l-=k;
        }
        return n1.next;
    }
    public static void main(String[] args){
       LinkTest s=new LinkTest();
       ListNode d1=new ListNode(1);
       ListNode d2=new ListNode(2);
       ListNode d3=new ListNode(3);
       ListNode d4=new ListNode(5);
       ListNode d5=new ListNode(7);
       ListNode d6=new ListNode(9);
       d1.next=d2;
       d2.next=d3;
       d3.next=d4;
       d4.next=d5;
       d5.next=d6;
      ListNode b=reverseKGroup(d1,2);
      ListNode h=b;
      System.out.println("每k个为一组翻转后链表为：");
      while(h!=null){
          System.out.print(h.val+" ");
          h=h.next;
      }
        }
}
